package com.clstu.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution12 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        //创建图
        Graph graph = Graph.createGreaph(numCourses,prerequisites);

        //每次找到入度为0的点,删除直到删完
        int[] res = new int[numCourses];
        int count = 0;
        while (!graph.nodes.isEmpty()) {
            Node dNode = null;
            for (Node n : graph.nodes) {
                if (n.in == 0) {
                    res[count++] = n.id;
                    dNode = n;
                    graph.deleteNode(n);
                }
            }
            //如果已经不存在入度为0的点,无解
            if (dNode == null) return new int[0];
        }

        return res;

    }

    public static class Graph{
        public List<Node> nodes =  null;

        public Graph(List<Node> ns){
            nodes = ns;
        }

        //创建图并返回
        public static Graph createGreaph(int n,int[][] edges){
            List<Node> ns = new ArrayList<>();
            for(int i=0;i<n;i++){
                ns.add(new Node(i));
            }

            //连接边
            for(int i=0;i<edges.length;i++){
                Node first = ns.get(edges[i][1]);
                Node second = ns.get(edges[i][0]);
                second.in++;
                first.nexts.add(second);
            }

            return new Graph(ns);
        }

        //删除节点以及它的影响
        public void deleteNode(Node n){
            nodes.remove(n);
            for(Node node:n.nexts){
                node.in--;
            }
        }
    }

    /**节点类
     */
    public static class Node{

        public int id ;
        public int in;
        public int out;
        List<Node> nexts;

        public Node(int id){
            this.id = id;
            nexts = new ArrayList<>();
        }
    }

    public static void main(String[] args) {
        int course = 2;
        int[][] preArr = {{1,0}};
//        int[] res = new Solution12().findOrder(course,preArr);
//        System.out.println(Arrays.toString(res));

        System.out.println("hello".startsWith("hel"));
        System.out.println(("hello".substring(3)));
    }
}
